Grokking Tree Coding Patterns for Interviews
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Course Overview
Introduction to Tree
Types of Tree
BST Traversal Techniques
BST Operations
Introduction to Level Order Traversal Pattern
Reverse Level Order Traversal (easy)
Solution: Reverse Level Order Traversal
Find Largest Value in Each Tree Row (medium)
Solution: Find Largest Value in Each Tree Row
Maximum Width of Binary Tree (medium)
Solution: Maximum Width of Binary Tree
Maximum Level Sum of a Binary Tree (medium)
Solution: Maximum Level Sum of a Binary Tree
Zigzag Traversal (medium)
Solution: Zigzag Traversal
Even Odd Tree (medium)
Solution: Even Odd Tree
N-ary Tree Level Order Traversal (hard)
Solution: N-ary Tree Level Order Traversal
Introduction to Tree Depth Pattern
Maximum Depth (or Height) of Binary Tree (easy)
Solution: Maximum Depth (or Height) of Binary Tree
Minimum Depth of a Binary Tree (easy)
Solution: Minimum Depth of a Binary Tree
Balanced Binary Tree (easy)
Solution: Balanced Binary Tree
Tree Diameter (easy)
Solution: Tree Diameter
Maximum Depth of N-ary Tree (easy)
Solution: Maximum Depth of N-ary Tree
Find maximum depth of subtree (medium)
Solution: Find maximum depth of subtree
Root to Leaf Path Pattern (medium)
Introduction to Root to Leaf Path Pattern
Binary Tree Paths (easy)
Solution: Binary Tree Paths
Sum of Root To Leaf Binary Numbers (easy)
Solution: Sum of Root To Leaf Binary Numbers
Insufficient Nodes in Root to Leaf Paths (medium)
Solution: Insufficient Nodes in Root to Leaf Paths
Smallest String Starting From Leaf (medium)
Solution: Smallest String Starting From Leaf
Pseudo-Palindromic Paths in a Binary Tree (medium)
Solution: Pseudo-Palindromic Paths in a Binary Tree
All Paths for a Sum (medium)
Solution: All Paths for a Sum
Sum of Path Numbers (medium)
Solution: Sum of Path Numbers
Path With Given Sequence (medium)
Solution: Path With Given Sequence
Count Paths for a Sum (medium)
Solution: Count Paths for a Sum
Leaf Processing Pattern (medium)
Introduction to Leaf Processing Pattern
Sum of Left Leaves (easy)
Solution: Sum of Left Leaves
Leaf-Similar Trees (easy)
Solution: Leaf-Similar Trees
Check if all leaves are at same level (medium)
Solution: Check if all leaves are at same level
Delete Leaves With a Given Value (medium)
Solution: Delete Leaves With a Given Value
Deepest Leaves Sum (medium)
Solution: Deepest Leaves Sum
Introduction to Tree View Pattern
Right View of a Binary Tree (medium)
Solution: Right View of a Binary Tree
Top View Of the Binary Tree (medium)
Solution: Top View Of the Binary Tree
Bottom View Of the Binary Tree (medium)
Solution: Bottom View Of the Binary Tree
Boundary of Binary Tree (medium)
Solution: Boundary of Binary Tree
Introduction to Comparison of Two Trees Pattern
Symmetric Tree (easy)
Solution: Symmetric Tree
Mirror Image Trees (medium)
Solution: Mirror Image Trees
Subtree of Another Tree (easy)
Solution: Subtree of Another Tree
Isomorphic Trees (medium)
Solution: Isomorphic Trees
Introduction to Serialize and Deserialize Tree Pattern
Serialize and Deserialize BST (medium)
Solution: Serialize and Deserialize BST
Verify Preorder Serialization of a Binary Tree (medium)
Solution: Verify Preorder Serialization of a Binary Tree
Create Binary Tree From Descriptions (medium)
Solution: Create Binary Tree From Descriptions
Serialize and Deserialize N-ary Tree (hard)
Solution: Serialize and Deserialize N-ary Tree
Solution: Check if all leaves are at same level

Problem Statement

Given a root of the binary tree, return true if all the leaf nodes of this tree exist at the same depth. Otherwise, return false.

Examples

Example 1:

  • Input: root = [1, 2, 3, 4, null, null, 5]
Image
  • Expected Output: true
  • Justification: The leaves are nodes 4 and 5, and they are both at the same level (level 3).

Example 2:

  • Input: root = [12, 20, 13, null, 10, 11, null, 16]
Image
  • Expected Output: false
  • Justification: The leaf node 11 is at depth 3 and leaf node 16 is at depth 4. So, both leaf nodes are at different depth.

Example 3:

  • Input: root = [10, 8, 15, 17, null, 12]
Image
  • Expected Output: true
  • Justification: The leaves are nodes 17, and 12, and all are located at the same level (level 3).

Solution

To solve this problem, we can use a depth-first search (DFS) traversal of the tree. DFS will allow us to explore the tree deeply, moving to the leaf nodes efficiently. During this traversal, we can keep track of the depth at which we encounter the first leaf node. As we visit each additional leaf, we compare its depth with that of the first leaf. If any leaf is found at a different depth, we know the leaves are not at the same level, and we can return false.

The advantage of DFS is that it traverses each path fully, allowing us to immediately detect depth differences without the need for additional tree traversals. This approach minimizes both time and space complexity by only requiring a single pass through the tree.

Step-by-step Algorithm

  1. Initialize referenceDepth:

    • Set referenceDepth to -1. This variable will store the depth of the first leaf node we find.
  2. Start DFS Traversal:

    • Begin the DFS traversal from the root of the tree, starting with depth 0.
  3. Handle empty trees:

    • If the current node is null, return true. This means there’s no node to process, and we can ignore this subtree.
  4. Check if the node is a leaf:

    • If the current node has no left or right children, it's a leaf node. For the first leaf node found, store its depth in referenceDepth.
    • If this is not the first leaf node, compare its depth to referenceDepth. If the depths matches, return true. Otherwise, return false.
  5. Continue DFS on children:

    • If the node is not a leaf, continue DFS on its left and right children, increasing the depth by 1 each time.
  6. Return the result:

    • Combine the returned value from the DFS traversal in the left and right subtree using the '&&' (and) operation, and return the final resultant boolean value.

Algorithm Walkthrough

Input: root = [1, 2, 3, 4, null, null, 5]

The binary tree looks like this:

       1
      / \
     2   3
    /     \
   4       5

We'll walk through the algorithm step by step:

  1. Start DFS from root (node 1) at depth 0.

    • Node 1 is not a leaf, so we move to its left and right children.
  2. DFS on left child of node 1 (node 2) at depth 1.

    • Node 2 is not a leaf, so we move to its left child.
  3. DFS on left child of node 2 (node 4) at depth 2.

    • Node 4 is a leaf. Since this is the first leaf encountered, set referenceDepth = 2.
  4. Backtrack to node 1 and DFS on right child of node 1 (node 3) at depth 1.

    • Node 3 is not a leaf, so we move to its right child as left child is null.
  5. DFS on right child of node 3 (node 5) at depth 2.

    • Node 5 is a leaf. Compare its depth (2) with referenceDepth (2). Since they match, we continue.
  6. All leaf nodes are at the same depth.

    • Both leaves (4 and 5) are at depth 2. Since no mismatch is found.

Final Output:

  • The function returns true, meaning all leaf nodes are at the same level in this tree.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity

The time complexity of the algorithm is , where n is the number of nodes in the binary tree. This is because the DFS traversal visits every node exactly once.

Space Complexity

The space complexity is , where h is the height of the binary tree. This comes from the recursion stack used by the DFS traversal. In the worst case (a skewed tree), the recursion depth can be equal to the total number of nodes in the tree and the overall space complexity can be .

Check if all leaves are at same level (medium)
Delete Leaves With a Given Value (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-step Algorithm

Algorithm Walkthrough

Final Output:

Code

Complexity Analysis

Time Complexity

Space Complexity